#include <stdlib.h>
#include <stdio.h>
  
typedef int bool;
#define true 1
#define false 0

   int m[8][8] = {0};
   int num = 0;
  
   bool check(int row,int column)
   {
       int i,j;
       if(row==1) 
		return true;
       //纵向只能有一枚皇后
       for(i=0;i<=row-2;i++)
       {
           if(m[i][column-1]==1) return false;
       }
       //左上至右下只能有一枚皇后
       i = row-2;
       j = i-(row-column);
       while(i>=0&&j>=0)
       {
           if(m[i][j]==1) return false;
           i--;
           j--;
       }
       //右上至左下只能有一枚皇后
       i = row-2;
       j = row+column-i-2;
       while(i>=0&&j<=7)
       {
           if(m[i][j]==1) return false;
           i--;
           j++;
       }
       return true;
   }
  
   //当已放置8枚皇后，为可行解时，输出棋盘
   void output()
   {
       int i,j;
       num++;
       printf("answer %d:\n",num);
       for(i=0;i<8;i++)
       {
           for(j=0;j<8;j++) printf("%d ",m[i][j]);
           printf("\n");
       }
   }
  
   //当棋盘前row-1行已放置好皇后，在第row行放置皇后
   void solve(int row)
   {
       int j;
       
       for (j=0;j<8;j++)
       {
        m[row-1][j] = 1;
        //检查在该列放置皇后是否可行
           if (check(row,j+1)==true)
           {
               //若该列可放置皇后，且该列为最后一列，则找到一可行解，输出
               if(row==8) output();
               //若该列可放置皇后，则向下一行，继续搜索、求解
               else solve(row+1);
           }
           //取出该列的皇后，进行回溯，在其他列放置皇后
           m[row-1][j] = 0;
       }
   }
  
   int main()
   {
       solve(1);
       return 0;
   }
